/* ------------------------------------------------------------------------
 *
 * geqo_erx.cpp
 *	 edge recombination crossover [ER]
 *
 * src/gausskernel/optimizer/geqo/geqo_erx.cpp
 *
 * -------------------------------------------------------------------------
 */
/* contributed by:
   =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
   *  Martin Utesch				 * Institute of Automatic Control	   *
   =							 = University of Mining and Technology =
   *  utesch@aut.tu-freiberg.de  * Freiberg, Germany				   *
   =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
 */
/* the edge recombination algorithm is adopted from Genitor : */
/*************************************************************/
/* 															 */
/* 	Copyright (c) 1990										 */
/* 	Darrell L. Whitley										 */
/* 	Computer Science Department								 */
/* 	Colorado State University								 */
/* 															 */
/* 	Permission is hereby granted to copy all or any part of  */
/* 	this program for free distribution.   The author's name  */
/* 	and this copyright notice must be included in any copy.  */
/* 															 */
/*************************************************************/

#include "postgres.h"
#include "knl/knl_variable.h"
#include "optimizer/geqo_recombination.h"
#include "optimizer/geqo_random.h"

static int gimme_edge(PlannerInfo* root, Gene gene1, Gene gene2, Edge* edge_table);
static void remove_gene(PlannerInfo* root, Gene gene, Edge edge, Edge* edge_table);
static Gene gimme_gene(PlannerInfo* root, Edge edge, Edge* edge_table);

static Gene edge_failure(PlannerInfo* root, Gene* gene, int index, Edge* edge_table, int num_gene);

/* alloc_edge_table
 *
 *	 allocate memory for edge table
 *
 */
Edge* alloc_edge_table(PlannerInfo* root, int num_gene)
{
    Edge* edge_table = NULL;

    /*
     * palloc one extra location so that nodes numbered 1..n can be indexed
     * directly; 0 will not be used
     */
    edge_table = (Edge*)palloc((num_gene + 1) * sizeof(Edge));

    return edge_table;
}

/* free_edge_table
 *
 *	  deallocate memory of edge table
 *
 */
void free_edge_table(PlannerInfo* root, Edge* edge_table)
{
    pfree_ext(edge_table);
}

/* gimme_edge_table
 *
 *	 fills a data structure which represents the set of explicit
 *	 edges between points in the (2) input genes
 *
 *	 assumes circular tours and bidirectional edges
 *
 *	 gimme_edge() will set "shared" edges to negative values
 *
 *	 returns average number edges/city in range 2.0 - 4.0
 *	 where 2.0=homogeneous; 4.0=diverse
 *
 */
float gimme_edge_table(PlannerInfo* root, Gene* tour1, Gene* tour2, int num_gene, Edge* edge_table)
{
    int i, index1, index2;
    int edge_total; /* total number of unique edges in two genes */

    /* at first clear the edge table's old data */
    for (i = 1; i <= num_gene; i++) {
        edge_table[i].total_edges = 0;
        edge_table[i].unused_edges = 0;
    }

    /* fill edge table with new data */
    edge_total = 0;

    for (index1 = 0; index1 < num_gene; index1++) {
        /*
         * presume the tour is circular, i.e. 1->2, 2->3, 3->1 this operaton
         * maps n back to 1
         */
        index2 = (index1 + 1) % num_gene;

        /*
         * edges are bidirectional, i.e. 1->2 is same as 2->1 call gimme_edge
         * twice per edge
         */
        edge_total += gimme_edge(root, tour1[index1], tour1[index2], edge_table);
        gimme_edge(root, tour1[index2], tour1[index1], edge_table);

        edge_total += gimme_edge(root, tour2[index1], tour2[index2], edge_table);
        gimme_edge(root, tour2[index2], tour2[index1], edge_table);
    }

    /* return average number of edges per index */
    return ((float)(edge_total * 2) / (float)num_gene);
}

/* gimme_edge
 *
 *	  registers edge from city1 to city2 in input edge table
 *
 *	  no assumptions about directionality are made;
 *	  therefor it is up to the calling routine to
 *	  call gimme_edge twice to make a bi-directional edge
 *	  between city1 and city2;
 *	  uni-directional edges are possible as well (just call gimme_edge
 *	  once with the direction from city1 to city2)
 *
 *	  returns 1 if edge was not already registered and was just added;
 *			  0 if edge was already registered and edge_table is unchanged
 */
static int gimme_edge(PlannerInfo* root, Gene gene1, Gene gene2, Edge* edge_table)
{
    int i;
    int edges;
    int city1 = (int)gene1;
    int city2 = (int)gene2;

    /* check whether edge city1->city2 already exists */
    edges = edge_table[city1].total_edges;

    for (i = 0; i < edges; i++) {
        if ((Gene)Abs(edge_table[city1].edge_list[i]) == city2) {
            /* mark shared edges as negative */
            edge_table[city1].edge_list[i] = 0 - city2;

            return 0;
        }
    }

    /* add city1->city2; */
    edge_table[city1].edge_list[edges] = city2;

    /* increment the number of edges from city1 */
    edge_table[city1].total_edges++;
    edge_table[city1].unused_edges++;

    return 1;
}

/* gimme_tour
 *
 *	  creates a new tour using edges from the edge table.
 *	  priority is given to "shared" edges (i.e. edges which
 *	  all parent genes possess and are marked as negative
 *	  in the edge table.)
 *
 */
int gimme_tour(PlannerInfo* root, Edge* edge_table, Gene* new_gene, int num_gene)
{
    int i;
    int edge_failures = 0;

    /* choose int between 1 and num_gene */
    new_gene[0] = (Gene)geqo_randint(root, num_gene, 1);

    for (i = 1; i < num_gene; i++) {
        /*
         * as each point is entered into the tour, remove it from the edge
         * table
         */
        remove_gene(root, new_gene[i - 1], edge_table[(int)new_gene[i - 1]], edge_table);

        /* find destination for the newly entered point */
        if (edge_table[new_gene[i - 1]].unused_edges > 0)
            new_gene[i] = gimme_gene(root, edge_table[(int)new_gene[i - 1]], edge_table);

        else { /* cope with fault */
            edge_failures++;

            new_gene[i] = edge_failure(root, new_gene, i - 1, edge_table, num_gene);
        }

        /* mark this node as incorporated */
        edge_table[(int)new_gene[i - 1]].unused_edges = -1;
    }

    return edge_failures;
}

/* remove_gene
 *
 *	 removes input gene from edge_table.
 *	 input edge is used
 *	 to identify deletion locations within edge table.
 *
 */
static void remove_gene(PlannerInfo* root, Gene gene, Edge edge, Edge* edge_table)
{
    int i, j;
    int possess_edge;
    int genes_remaining;

    /*
     * do for every gene known to have an edge to input gene (i.e. in
     * edge_list for input edge)
     */
    for (i = 0; i < edge.unused_edges; i++) {
        possess_edge = (int)Abs(edge.edge_list[i]);
        genes_remaining = edge_table[possess_edge].unused_edges;

        /* find the input gene in all edge_lists and delete it */
        for (j = 0; j < genes_remaining; j++) {
            if ((Gene)Abs(edge_table[possess_edge].edge_list[j]) == gene) {
                edge_table[possess_edge].unused_edges--;

                edge_table[possess_edge].edge_list[j] = edge_table[possess_edge].edge_list[genes_remaining - 1];

                break;
            }
        }
    }
}

/* gimme_gene
 *
 *	  priority is given to "shared" edges
 *	  (i.e. edges which both genes possess)
 *
 */
static Gene gimme_gene(PlannerInfo* root, Edge edge, Edge* edge_table)
{
    int i;
    Gene frnd;
    int minimum_edges;
    int minimum_count = -1;
    int rand_decision;
    const int EDGES_SIZE = 5;

    /*
     * no point has edges to more than 4 other points thus, this contrived
     * minimum will be replaced
     */
    minimum_edges = EDGES_SIZE;

    /* consider candidate destination points in edge list */
    for (i = 0; i < edge.unused_edges; i++) {
        frnd = (Gene)edge.edge_list[i];

        /*
         * give priority to shared edges that are negative; so return 'em
         */
        /*
         * negative values are caught here so we need not worry about
         * converting to absolute values
         */
        if (frnd < 0)
            return (Gene)Abs(frnd);

        /*
         * give priority to candidates with fewest remaining unused edges;
         * find out what the minimum number of unused edges is
         * (minimum_edges); if there is more than one cadidate with the
         * minimum number of unused edges keep count of this number
         * (minimum_count);
         */
        /*
         * The test for minimum_count can probably be removed at some point
         * but comments should probably indicate exactly why it is guaranteed
         * that the test will always succeed the first time around.  If it can
         * fail then the code is in error
         */
        if (edge_table[(int)frnd].unused_edges < minimum_edges) {
            minimum_edges = edge_table[(int)frnd].unused_edges;
            minimum_count = 1;
        } else if (minimum_count == -1)
            ereport(ERROR,
                (errmodule(MOD_OPT), errcode(ERRCODE_OPTIMIZER_INCONSISTENT_STATE), errmsg("minimum_count not set")));
        else if (edge_table[(int)frnd].unused_edges == minimum_edges)
            minimum_count++;
    }

    /* random decision of the possible candidates to use */
    rand_decision = geqo_randint(root, minimum_count - 1, 0);

    for (i = 0; i < edge.unused_edges; i++) {
        frnd = (Gene)edge.edge_list[i];

        /* return the chosen candidate point */
        if (edge_table[(int)frnd].unused_edges == minimum_edges) {
            minimum_count--;

            if (minimum_count == rand_decision)
                return frnd;
        }
    }

    /* ... should never be reached */
    ereport(ERROR,
        (errmodule(MOD_OPT),
            errcode(ERRCODE_OPTIMIZER_INCONSISTENT_STATE),
            errmsg("neither shared nor minimum number nor random edge found")));
    return 0; /* to keep the compiler quiet */
}

/* edge_failure
 *
 *	  routine for handling edge failure
 *
 */
static Gene edge_failure(PlannerInfo* root, Gene* gene, int index, Edge* edge_table, int num_gene)
{
    int i;
    Gene fail_gene = gene[index];
    int remaining_edges = 0;
    int four_count = 0;
    int rand_decision;
    const int TOTAL_EDGES_COUNT = 4;

    /*
     * how many edges remain? how many gene with four total (initial) edges
     * remain?
     */
    for (i = 1; i <= num_gene; i++) {
        if ((edge_table[i].unused_edges != -1) && (i != (int)fail_gene)) {
            remaining_edges++;

            if (edge_table[i].total_edges == TOTAL_EDGES_COUNT)
                four_count++;
        }
    }

    /*
     * random decision of the gene with remaining edges and whose total_edges
     * == 4
     */
    if (four_count != 0) {
        rand_decision = geqo_randint(root, four_count - 1, 0);
        for (i = 1; i <= num_gene; i++) {
            if ((Gene)i != fail_gene && edge_table[i].unused_edges != -1 && edge_table[i].total_edges == TOTAL_EDGES_COUNT) {
                four_count--;

                if (rand_decision == four_count)
                    return (Gene)i;
            }
        }

        elog(LOG, "no edge found via random decision and total_edges == 4");
    } else if (remaining_edges != 0) {
        /* random decision of the gene with remaining edges */
        rand_decision = geqo_randint(root, remaining_edges - 1, 0);

        for (i = 1; i <= num_gene; i++) {
            if ((Gene)i != fail_gene && edge_table[i].unused_edges != -1) {
                remaining_edges--;

                if (rand_decision == remaining_edges) {
                    return i;
                }
            }
        }

        elog(LOG, "no edge found via random decision with remaining edges");
    } else {  
        /*
         * edge table seems to be empty; this happens sometimes on the last point
         * due to the fact that the first point is removed from the table even
         * though only one of its edges has been determined
         *
         * occurs only at the last point in the tour;
         * simply look for the point which is not yet used 
         */
        for (i = 1; i <= num_gene; i++)
            if (edge_table[i].unused_edges >= 0)
                return (Gene)i;

        elog(LOG, "no edge found via looking for the last ununsed point");
    }

    /* ... should never be reached */
    ereport(ERROR, (errmodule(MOD_OPT), errcode(ERRCODE_OPTIMIZER_INCONSISTENT_STATE), errmsg("no edge found")));
    return 0; /* to keep the compiler quiet */
}
